package com.shexianyu.simple;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * @author shexianyu
 * @desc 1005. K 次取反后最大化的数组和
 * @date 2021/12/3
 */
public class LargestSumAfterKNegations {

    /**
     * 解法1
     *
     * @param nums
     * @param k
     * @return
     */
    public int largestSumAfterKNegations(int[] nums, int k) {

        int index = 0;
        int max = 0;
        //变换次数
        for (int m = 0; m < k; m++) {
            int min = nums[0];
            //找出最小值
            for (int i = 0; i < nums.length; i++) {
                min = Math.min(min, nums[i]);
            }
            //寻找最小值索引
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] == min) {
                    index = i;
                    break;
                }
            }
            //取反赋值
            nums[index] = (-1 * min);
        }
        //将数组值进行累加
        for (int i = 0; i < nums.length; i++) {
            max += nums[i];
        }
        return max;
    }

    /**
     * 解法2
     *
     * @param nums
     * @param k
     * @return
     */
    public int largestSumAfterKNegations1(int[] nums, int k) {
        for (int i = 0; i < k; i++) {
            Arrays.sort(nums);
            nums[0] = (-1) * nums[0];
        }
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        return sum;
    }

    /**
     * 官方题解
     *
     * @param nums
     * @param k
     * @return
     */
    public int largestSumAfterKNegations2(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<Integer, Integer>();
        for (int num : nums) {
            freq.put(num, freq.getOrDefault(num, 0) + 1);
        }
        int ans = Arrays.stream(nums).sum();
        for (int i = -100; i < 0; ++i) {
            if (freq.containsKey(i)) {
                int ops = Math.min(k, freq.get(i));
                ans += (-i) * ops * 2;
                freq.put(i, freq.get(i) - ops);
                freq.put(-i, freq.getOrDefault(-i, 0) + ops);
                k -= ops;
                if (k == 0) {
                    break;
                }
            }
        }
        if (k > 0 && k % 2 == 1 && !freq.containsKey(0)) {
            for (int i = 1; i <= 100; ++i) {
                if (freq.containsKey(i)) {
                    ans -= i * 2;
                    break;
                }
            }
        }
        return ans;
    }
}
